Certain dynamic programming concepts have been effective in minimizing interconnect delays in rooted tree topologies. Referring to FIG. 1, an example rooted tree 6 may be characterized by a single source 8 connected to an input node 10, and an output node 12. The output node 12 is connected to multiple destination nodes 14, 16, 18 on sinks 15, 17, 19, respectively, via internal nodes 20, 22, 24, 26, 28, 30, 32 and edges (segments of interconnect between two adjacent nodes or between a node and branch point).
An electrical signal is allowed to propagate from the input of the driver 8 to the destination nodes 14, 16, 18. Each of the edges may be characterized by a resistance Re and a capacitance Ce. Each of the destination nodes 14, 16, 18 may be characterized by a capacitance csink and a required arrival time qsink, or equivalently, by a (c, q) pair (tuple), where c=csink and q=qsink. An electrical signal propagating from the source node 10 to the destination nodes 14, 16, 18 experiences delays along the driver and RC network. This may result in different accumulated delays to the different destinations.
Performance and/or cycle-time requirements of a typical microprocessor, for example, may require that the signal reaches the destination nodes 14, 16, 18 at pre-specified times (required arrival times). The signal, however, may fail to arrive at one or more destinations within the specified time. These violations of required arrival times can be alleviated by locating repeaters from the list 36a-36m and 38a-38n (also known as inverting or non-inverting buffers) at some of the internal nodes 20-32. Repeaters are thus to be selected from a given library 40 of sizes and polarities. A goal of repeater insertion can be to reduce the maximum violation in the required arrival time at the driver. Other goals could include minimizing power (area) subject to constraints on signal arrival times at the destinations.
Traditional dynamic optimization techniques are restricted to a rooted tree structure representing an RC network. They may fail to capture certain constraints, such as timing optimization in a hierarchical design, or may not be applicable in logic networks with multiple input gates.